// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Dijkstra's shortest path using a graph
namespace ConsoleApp1
{
    class Program
    {
        static List<string> dijkstra(Dictionary<string, Dictionary<string, int>> graph, string start, string goal)
        {
            // Initialise
            int infinity = int.MaxValue;
            Dictionary<string, int> distance = new Dictionary<string, int>();
            Dictionary<string, string> previous_vertex = new Dictionary<string, string>();
            List<string> shortest_path = new List<string>();
            string shortest;
            int cost;

            // Set the shortest distance from the start for all vertices to infinity
            foreach (var vertex in graph)
            {
                distance.Add(vertex.Key, infinity);
            }
            // Set the shortest distance from the start for the start vertex to 0
            distance[start] = 0;

            // Loop until all the vertices have been visited
            while (graph.Count > 0)
            {
                // Find the vertex with the shortest distance from the start
                shortest = null;
                foreach (var vertex in graph)
                {
                    if (shortest == null)
                    {
                        shortest = vertex.Key;
                    }
                    else if (distance[vertex.Key] < distance[shortest])
                    {
                        shortest = vertex.Key;
                    }
                }

                // Calculate shortest distance for each edge
                foreach (var neighbour in graph[shortest])
                {
                    cost = neighbour.Value;
                    // Update the shortest distance for the vertex if the new value is lower
                    if (graph.ContainsKey(neighbour.Key) && cost + distance[shortest] < distance[neighbour.Key])
                    {
                        distance[neighbour.Key] = cost + distance[shortest];
                        previous_vertex[neighbour.Key] = shortest;
                    }
                }

                // The vertex has now been visited, remove it from the vertices to consider
                graph.Remove(shortest);
            }
            // Generate the shortest shortest path
            // Start from the goal, adding vertices to the front of the list
            string current_vertex = goal;
            while (current_vertex != start)
            {
                shortest_path.Insert(0, current_vertex);
                current_vertex = previous_vertex[current_vertex];
            }
            // Add the start vertex
            shortest_path.Insert(0, start);

            // Return the shortest path
            return shortest_path;
        }
        // Main program starts here
        static void Main(string[] args)
        {
            var graph = new Dictionary<string, Dictionary<string, int>>()
            {
                { "A", new Dictionary<String, int>() { { "B", 4 }, { "C", 3 }, { "D", 2 } } },
                { "B", new Dictionary<String, int>() { { "A", 4 }, { "E", 4 } } },
                { "C", new Dictionary<String, int>() { { "A", 2 }, { "D", 5 } } },
                { "D", new Dictionary<String, int>() { { "A", 2 }, { "C", 5 }, { "F", 2 } } },
                { "E", new Dictionary<String, int>() { { "B", 4 }, { "G", 2 } } },
                { "F", new Dictionary<String, int>() { { "D", 2 }, { "G", 10 } } },
                { "G", new Dictionary<String, int>() { { "E", 2 }, { "F", 10 } } }
            };

            // Precalculated heuristics
            var h = new Dictionary<string, int>()
            {
                {"A", 12}, {"B", 6}, {"C", 9}, {"D", 12}, {"E", 3}, {"F", 9}, {"G", 0}
            };

            List<string> optimal_path = new List<string>();
            optimal_path = dijkstra(graph, "A", "G");
            Console.WriteLine(string.Join(", ", optimal_path));
        }
    }
}
